package lsprse;

import java.io.InputStream;
import java.util.Stack;

class Parser {
   
 
    ///////////////////////////////////////////////
    // Interface function for parsing
    ////
    public static Object parse(InputStream is) {
        Parser parser= new Parser(is);
        parser.next();
        Object[] parsed = parser.parse(0);
        printWithLines(parsed, null);
        printWithHead(parsed);
        println("");
        return stringify(parsed);
    }

 

    public static void printWithLines(Object o, String tabs)
    {
       if(tabs == null)
          tabs = new String();
       
       if(o instanceof Object[])
       {
          Object[] list = (Object[])o;
          println(tabs + list[0]);
          tabs += "   ";
          for(int i = 1; i < list.length; i++)
             printWithLines(list[i], tabs);
       }
       else
          println(tabs + o);
       
    }

    public static void printWithHead(Object o)
    {
       
       if(o instanceof Object[])
       {
          Object[] list = (Object[])o;
          
          print(list[0]);
          print("[");         
          for(int i = 1; i < list.length; i++)
          {
             if(i > 1)
                print(" ");
             printWithHead(list[i]);
          }
          print("]");
       }
       else
       {
          print(o);
       }
    }

    public static void print(Object o)
    {
       System.out.print(o.toString());
    }
    public static void print(String s)
    {
       System.out.print(s);
    }
    
    public static void println(String s)
    {
       System.out.println(s);
    }
    
    public static String stringify(Object o) {
       if(o instanceof Object[]) {
           Object[] os = (Object[])o;
           StringBuffer sb = new StringBuffer();
           sb.append("[");

           for(int i = 0; i < os.length; i++) {
               sb.append(" ");
               sb.append(stringify(os[i]));
           }
           sb.append(" ]");
           return sb.toString();
       } else {
           return o.toString();
       }
   }
    /////////////////////////////////////////////
    // The core parse function
    ////////
    private Object[] parse(int rbp) {
        Token t = token;
        next();
        Object[] left = t.nud();
        while(rbp < token.bp && !t.sep) {
            t = token;
            next();
            left = t.led(left);
        }
        return left;
    }


    private static Object [] v(Object o1, Object o2) { 
        Object[] result = {o1, o2};
        return result;
    }

    private static Object [] v(Object o1, Object o2, Object o3) {
        Object[] result = {o1, o2, o3};
        return result;
    }

    //////////////////////////////////////////
    // Tokeniser
    ////

    InputStream is;
    char c;
    StringBuffer sb;
    Token token;

    private Object getToken() {
        return token;
    }

    private Parser(InputStream is) {
        this.is = is;
        sb = new StringBuffer();
        c = ' ';
        token = null;
    }

    private void nextc() {
        try {
            c = (char)is.read();
        } catch(Exception e) {
            c = (char)-1;
        }
    }
    private void pushc() {
        sb.append((char)c);
        nextc();
    }
    private boolean isNum() {
        return '0' <= c && c <= '9';
    }

    private boolean isAlphaNum() {
        return isNum() || c == '_' || ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z');
    }

    private boolean isSymb() {
        return c == '=' || c == '!' || c == '<' || c == '&' || c == '|';
    }

    
    private boolean next() {
        sb.setLength(0);

        boolean isComment = skipWhiteSpace();
        if(isComment)
           return true;

        // End of file
        if(c == -1) {
            token = new Token(false, null);
            return false;

        // String
        } else if(c == '"') {
            nextc();
            while(c != -1 && c != '"') {
                if(c == '\\') {
                    nextc();
                    if(c == 'n') {
                        c = '\n';
                    }
                }
                pushc();
            }
            nextc();
            token = new Token(true, sb.toString());
            return true;

        // Number
        } else if(isNum()) {
            do {
                pushc();
            } while(isNum());
            token = new Token(true, Integer.valueOf(sb.toString()));
            return true;

        // Identifier
        } else if(isAlphaNum()) {
            do {
                pushc();
            } while(isAlphaNum());

        // Long symbol !== , ===, <= , &&, ...
        } else if(isSymb()) {
            do {
                pushc();
            } while(isSymb());

        // Single symbol
        } else {
            pushc();
        }
        token = new Token(false, sb.toString());
        return true;
    }

    
    //skip whitespace and single line comments
    //return true if its a comment
    private boolean skipWhiteSpace()
    {
       // skip whitespaces
       while(c == ' ' || c == '\n' || c == '\t' || c == '\r' || c == '/') {
           // comments
           if(c == '/') {
               nextc();
               if(c == '/') {
                   while(c != '\n' && c != -1) {
                       nextc();
                   }
               } else {
                   token = new Token(false, "/");
                   return true;
               }
           }
           nextc();
       }
       return false;
    }

    
    ////////////////////////////////////////////////////////
    // Token class
    // nuds/leds
    ////

    private static final Object[] END_TOKEN = { "(end)" };
    private static final Object[] SEP_TOKEN = { "(sep)" };
    private static final String ID_APPLY= "apply";
    private static final Boolean TRUE = new Boolean(true);

    private enum NudId
    {
       NUD_IDENTIFIER,
       NUD_LITERAL,
       NUD_END,
       NUD_SEP,
       NUD_LIST,
       NUD_PREFIX,
       NUD_PREFIX2;
    }

    private enum LedId
    {
       LED_NULL,
       LED_INFIX,
       LED_INFIXR,
       LED_INFIX_LIST
    }

    class Token {
        Object val; // coukd be a string, an Integer or a Boolean
        private NudId nudId;
        private LedId ledId;
        public boolean sep;
        public int bp;


        private Object[] readList(Stack s) {
            Object[] p = parse(0);
            while(p != END_TOKEN) {
                if(p != SEP_TOKEN) {
                    s.push(p);
                }
                p = parse(0);
            }

            Object[] result = new Object[s.size()];
            s.copyInto(result);
            return result;
        }
        public Object[] nud() {
            switch(nudId) {
                case NUD_IDENTIFIER:
                    return v("identifier", val);
                case NUD_LITERAL:
                    return v("literal", val);
                case NUD_END:
                    return END_TOKEN;
                case NUD_SEP:
                    return SEP_TOKEN;
                case NUD_LIST:
                    {
                      Stack s = new Stack();
                        s.push(val);
                        return readList(s);
                    }
                case NUD_PREFIX:
                    return v(val, parse(0));
                case NUD_PREFIX2:
                    return v(val, parse(0), parse(0));
                default:
                    throw new Error("Unknown nud: " + nudId);
            }
        }
        public Object[] led(Object left) {
            switch(ledId) {
                case LED_INFIX:
                    return v(val, left, parse(bp));
                case LED_INFIXR:
                    return v(val, left, parse(bp-1));
                case LED_INFIX_LIST:
                    {
                        Stack<Object> s = new Stack<Object>();
                        s.push(ID_APPLY);
                        s.push(val);
                        s.push(left);
                        return readList(s);
                    }
                default:
                    throw new Error("Unknown led: " + ledId);
            }
        }

        public Token(boolean isLiteral, Object val) {
            this.val = val;
            sep = false;
            bp = 0;
            nudId = NudId.NUD_IDENTIFIER;
            ledId = LedId.LED_NULL;
            if(isLiteral) {
                nudId = NudId.NUD_LITERAL;

                return;
            }

            if( ".".equals(val)) {
                bp = 700;
                ledId = LedId.LED_INFIX;

            }

            if( "(".equals(val)
             || "[".equals(val)) {
                bp = 600;
                ledId = LedId.LED_INFIX_LIST;
            }

            if( "*".equals(val)
             || "%".equals(val)) {
                bp = 500;
                ledId = LedId.LED_INFIX;
            }

            if( "+".equals(val)
             || "-".equals(val)) {
                bp = 400;
                ledId = LedId.LED_INFIX;

            }

            if( "===".equals(val)
             || "!==".equals(val)
             || "<=".equals(val)
             || "<".equals(val)) {
                bp = 300;
                ledId = LedId.LED_INFIX;
            }

            if( "&&".equals(val)
             || "||".equals(val)
             || "else".equals(val)) {
                bp = 200;
                ledId = LedId.LED_INFIXR;
            }

            if( "=".equals(val)) {
                bp = 100;
                ledId = LedId.LED_INFIX;
            }

            if( val == null
             || "]".equals(val)
             || ")".equals(val)
             || "}".equals(val) ) {
                nudId = NudId.NUD_END;
                sep = true;
            }

            if( ":".equals(val)
             || ";".equals(val)
             || ",".equals(val) ) {
                nudId = NudId.NUD_SEP;
                sep = true;
            }

            if( "(".equals(val)
             || "{".equals(val)
             || "[".equals(val) ) {
                nudId = NudId.NUD_LIST;
            }

            if( "var".equals(val)
             || "return".equals(val)
             || "-".equals(val)
             || "!".equals(val) ) {
                nudId = NudId.NUD_PREFIX;
            }

            if( "function".equals(val)
             || "if".equals(val)
             || "while".equals(val) ) {
                nudId = NudId.NUD_PREFIX2;
            }

            if( "undefined".equals(val)
             || "null".equals(val)
             || "false".equals(val)) {
                val = null;
                nudId = NudId.NUD_LITERAL;
            }
            if( "true".equals(val) ) {
                val = TRUE;
                nudId = NudId.NUD_LITERAL;
            }

        }
        public String toString() {
            return val.toString();
        }

    }

}